from collections import deque


class TreeNode:
    def __init__(self, x=0):
        self.val = x
        self.left = None
        self.right = None


def f(root: TreeNode):
    """
    递归遍历
    :param root:
    :return:
    """
    if not root:
        return
    print(root.val, end=" ")
    f(root.left)
    f(root.right)


def pre_order(root: TreeNode):
    """
    先序遍历，非递归
    :param root:
    :return:
    """
    if not root:
        return
    lst = []
    lst.append(root)
    while lst:
        node = lst.pop()
        print(node.val)
        if node.right:
            lst.append(node.right)
        if node.left:
            lst.append(node.left)


def post_order(root: TreeNode):
    """
    后序遍历，非递归
    :param root:
    :return:
    """
    if not root:
        return
    tmp = []
    res = []
    tmp.append(root)
    while tmp:
        node = tmp.pop()
        res.append(node)
        if node.left:
            tmp.append(node.left)
        if node.right:
            tmp.append(node.right)
    for i in res:
        print(i.val, end=" ")


def mid_order(root: TreeNode):
    """
    中序遍历，非递归
    :param root:
    :return:
    """
    if not root:
        return
    stack = []
    while stack or root:
        if root:
            stack.append(root)
            root = root.left
        else:
            root = stack.pop()
            print(root.val, end=" ")
            root = root.right


def level_order(root: TreeNode):
    """
    层序遍历，非递归
    :param root:
    :return:
    """
    if not root:
        return
    queue = deque()
    queue.append(root)
    while queue:
        node = queue.popleft()
        print(node.val, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)


if __name__ == "__main__":
    head = TreeNode(6)
    head.left = TreeNode(3)
    head.left.left = TreeNode(1)
    head.left.left.right = TreeNode(2)
    head.left.right = TreeNode(4)
    head.left.right.right = TreeNode(5)
    head.right = TreeNode(9)
    head.right.left = TreeNode(8)
    head.right.left.left = TreeNode(7)
    head.right.right = TreeNode(10)

    level_order(head)